//
// Description: 621. 任务调度器
// Created by Loading on 2022/9/4.
//

#include <bits/stdc++.h>

using namespace std;

int leastInterval(vector<char> &tasks, int n) {
    if (n == 0) {
        return tasks.size();
    }

    // 统计各任务数量
    unordered_map<char, int> cnt;
    for (auto c : tasks) {
        ++cnt[c];
    }

    // 每个任务下一次最早执行的时间，剩余执行次数
    vector<int> nextTime, rest;
    for (auto[_, v] : cnt) {
        nextTime.emplace_back(1);
        rest.emplace_back(v);
    }

    int m = cnt.size();
    int time = 0;
    for (int i = 0; i < tasks.size(); ++i) {
        ++time;
        int minNextTime = INT_MAX;
        for (int j = 0; j < m; ++j) {
            // 寻找未执行完且下一次执行时间最早的任务的执行时间
            if (rest[j]) {
                minNextTime = min(minNextTime, nextTime[j]);
            }
        }
        // 更新time，跳过冷却期
        time = max(time, minNextTime);
        int t = -1;
        for (int j = 0; j < m; ++j) {
            // 寻找符合执行时间的剩余执行次数最多的任务
            if (rest[j] && nextTime[j] <= time) {
                if (t == -1 || rest[t] < rest[j]) {
                    t = j;
                }
            }
        }

        // 更新选中任务的下一次执行时间和剩余执行次数
        nextTime[t] = time + n + 1;
        --rest[t];
    }

    return time;
}

int main() {
    vector<char> tasks{'A', 'A', 'A', 'B', 'B', 'B'};
    int n = 2;
    int res = leastInterval(tasks, n);

    cout << res << endl;

    return 0;
}
